/***************************************************************************************************
  *Copyright(C),2010-2017,Sumscope
  *FileName	:  pinyin_search_set.h
  *Author	:  scofined.qi
  *Version	:  1.0
  *Date		:  2017/06/04
  *Desc		:  //用于主要说明此程序文件完成的主要功能
  *Relation :  
  *Others	:  //其他内容说明
  *Function :  //主要函数列表，每条记录应包含函数名及功能简要说明
  *History	:  //修改历史记录列表，每条修改记录应包含修改日期、修改者及修改内容简介
***************************************************************************************************/
#pragma once

#include "pinyin_search_define.h"

#include <map>

namespace qb{
	namespace base{
		namespace internal{
			class InverseSetOld {
			public:
				typedef unsigned char uchar;
                typedef std::map<int, uchar> Base;
				typedef Base::iterator iterator;
				typedef Base::const_iterator const_iterator;
			protected:
				Base		m_map;			// value 是一个债券的所有字段出现此key的个数,最大不会超过256
				int			m_max;			// 最大长度
			public:
				InverseSetOld() :m_max(1){}
				void reset(){ m_map.clear(); m_max = 0; }
				iterator begin(){ return m_map.begin(); }
				iterator end(){ return m_map.end(); }
				const_iterator cbegin()const{ return m_map.cbegin(); }
				const_iterator cend()const{ return m_map.cend(); }
				int size()const{ return m_map.size(); }
				int getmax()const{ return m_max; }
				bool empty()const{ return m_map.empty(); }
				void add(int key)
				{
					iterator it = m_map.find(key);
					if (it != m_map.end())
					{
						it->second++;
						m_max = m_max < it->second ? it->second : m_max;
					}
					else
						m_map.insert(Base::value_type(key, 1));
				}
				void remove(int key)
				{
					iterator it = m_map.find(key);
					if (it != m_map.end())
					{
						it->second--;
						if (it->second <= 0)
							m_map.erase(it);
					}
				}
				bool exist(int key)const
				{
					const_iterator it = m_map.find(key);
					return it != m_map.end();
				}
				void intersect(const InverseSetOld& op)
				{
					for (iterator it = begin(); it != end();)
					{
						if (!op.exist(it->first))
							it = m_map.erase(it);
						else
							++it;
					}
				}
				bool copy(int* indexes, int& capcity)
				{
					int* pint = indexes;
					int* pend = indexes + capcity;
					for (const_iterator it = m_map.begin(); it != m_map.end() && pint < pend; ++it)
					{
						*pint++ = it->first;
					}
					capcity = m_map.size();
					return true;
				}
			};

			/*
				使用数组来模仿map,原因:节省大量内存
				IndexId的高24位,是key,真实身份是债券索引,最大值为2^24=16777216
				低8位,表示对应key的计数,最大计数为255,超过此值可能出现问题
			*/
			class InverseSetNew2 {
			public:
				enum{ ROUND_SIZE = 32,	//默认的KeyCount数组分配长度
				};
				typedef unsigned int uint;
				typedef uint KeyType;
				typedef uint CountType;
				//static __forceinline unsigned int makeid(int key, int val){ return (key << 8) | (val & 0x000000ff); }
				//static __forceinline int getkey(unsigned int ii){ return (ii & 0xffffff00) >> 8; }
				//static __forceinline int getval(unsigned int ii){ return ii & 0x000000ff; }
				class KeyCount{
					uint	m_count : kIndexId::CountBits;
					uint	m_key : kIndexId::KeyBits;
				public:
					KeyCount():m_key(0),m_count(0){}
					KeyCount(KeyType k, CountType c) :m_key(k), m_count(c){}
                    bool operator==(const KeyCount& ii)const{ return m_key == ii.m_key && m_count == ii.m_count; }
                    KeyType getkey()const{ return m_key; }
                    CountType getval()const{ return m_count; }
                    CountType addval(){ m_count++; return m_count; }
                    CountType decval(){ m_count--; return m_count; }
                    uint get()const{return  ((uint(m_key)) << kIndexId::CountBits) | (uint)m_count; }
				};
				
				//typedef unsigned int IndexId;
				typedef InverseSetNew2 Base;
				typedef KeyCount value_type;
			protected:
				KeyCount*		m_first;		// 按照bid递增
				int				m_count;		// 数组m_first的实际长度
				int				m_capcity;		// 数组m_first的容量
				CountType		m_max;			// 最大长度,按设计不能超过255
			public:
				class iterator{
					int	m_index;
					const Base* m_owner;
				public:
					KeyType	first;
					CountType	second;
				public:
					explicit iterator(const Base* owner, int index){ m_owner = owner; m_index = index; owner->get(index, first, second); }
					iterator(const iterator& it) :m_owner(it.m_owner), m_index(it.m_index), first(it.first), second(it.second){}
					iterator& operator++(){ m_index++; m_owner->get(m_index, first, second); return *this; }
					bool operator!=(const iterator& ci)const{ return m_owner != ci.m_owner || m_index != ci.m_index; }
					iterator* operator->(){ return this; }
				};
				class const_iterator{
					int	m_index;
					const Base* m_owner;
				public:
					KeyType	first;
					CountType	second;
				public:
					explicit const_iterator(const Base* owner, int index){ m_owner = owner; m_index = index; owner->get(index, first, second); }
					const_iterator(const const_iterator& it) :m_owner(it.m_owner), m_index(it.m_index), first(it.first), second(it.second){}
					const_iterator& operator++(){ m_index++; m_owner->get(m_index, first, second); return *this; }
					bool operator!=(const const_iterator& ci)const{ return m_owner != ci.m_owner || m_index != ci.m_index; }
					const_iterator* operator->(){ return this; }
				};
			public:
				static void Clear();
				InverseSetNew2();

				~InverseSetNew2();

				void reset(){m_count = 0;m_max = 1;}
				iterator begin(){ return iterator(this, 0); }
				iterator end(){ return iterator(this, m_count); }
				const_iterator cbegin()const{ return const_iterator(this, 0); }
				const_iterator cend()const{ return const_iterator(this, m_count); }
				const KeyCount& at(int index)const{ return m_first[index]; }

				int size()const{ return m_count; }
				int capcity()const{ return m_capcity; }
				int getmax()const{ return m_max; }
				bool empty()const{ return m_count <= 0; }

				bool add(KeyType key);

				void remove(KeyType key);
				bool exist(KeyType key) const;

				void intersect(const Base& iis);

				void expand(int cap = -1);
				bool shrink(int delta=16);
				void check(unsigned int maxkey);
				bool get(int index, KeyType& key, CountType& val)const;

				int find(int key, int npos)const;
				const KeyCount* GetData()const{ return m_first; }
			protected:
				int find_fast(KeyType key, int npos)const;
				int find_slow(KeyType key, int npos) const;
				int find(KeyType key,int npos) const;
				int find_old(KeyType key, int npos) const;
				
			};

			typedef InverseSetNew2 InverseSet;
			class IndexIdRange {
			public:
				InverseSet*		m_memory_set;		// 内存中的集合
				int				m_offset;			// 在映射文件中的偏移量
				int				m_bytes;			// 
				int				m_length;			// 个数
			public:
				IndexIdRange(InverseSet* iset) :m_memory_set(iset), m_offset(0), m_length(0), m_bytes(0){}
			};
		}
	}
}
